package com.gitee.feizns.explore.data_structure.linked_list.singly;

import java.util.HashSet;
import java.util.Set;

/**
 * 面试题 02.01. 移除重复节点
 * @author feizns
 * @since 2020/3/4
 */
public class RemoveDuplicateNodes {

    private static ListNode create() {
        ListNode r = new ListNode(1);
        r.next = new ListNode(2);
        r.next.next = new ListNode(3);
        r.next.next.next = new ListNode(3);
        r.next.next.next.next = new ListNode(2);
        r.next.next.next.next.next = new ListNode(1);
        return r;
    }

    public static void main(String[] args) {
        ListNode node = removeDuplicateNodes(create());
        println(node);
    }
    private static void println(ListNode n) {
        if ( n != null ) {
            System.out.print(n.val);
            println(n.next);
        }
    }

    static Set<Integer> VAL = new HashSet<>();

    private static ListNode helper(ListNode head) {
        if ( head != null ) {
            if ( head.next != null ) {
                if ( VAL.contains(head.next.val) ) {
                    head.next = head.next.next;
                    helper(head);
                } else {
                    VAL.add(head.next.val);
                    head.next = helper(head.next);
                }
            }
        }
        return head;
    }

    public static ListNode removeDuplicateNodes(ListNode head) {
        if ( head != null )
            VAL.add(head.val);
        return helper(head);
    }

}
